
#ifdef a

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

void MergeData(int* arr, int left, int mid, int right, int* temp) {
	int begin1, end1, begin2, end2;
	begin1 = left, end1 = mid;
	begin2 = mid, end2 = right;
	int index = left;
	while (begin1 < end1 && begin2 < end2) {
		if (arr[begin1] <= arr[begin2])//等于号--》稳定
			temp[index++] = arr[begin1++];
		else
			temp[index++] = arr[begin2++];
	}
	while (begin1 < end1)
		temp[index++] = arr[begin1++];
	while (begin2 < end2)
		temp[index++] = arr[begin2++];
	return;
}
void MergeSort(int* arr, int left, int right, int* temp) {
	if (right - left <= 1)
		return;
	int mid = left + ((right - left) >> 1);
	MergeSort(arr, left, mid, temp);
	MergeSort(arr, mid, right, temp);

	//归并
	MergeData(arr, left, mid, right, temp);
	
	memcpy(arr + left, temp + left, sizeof(arr[0]) * (right - left));
}

void SortPrint(int* arr, int size) {
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

//归并排序稳定性：稳定
//时间复杂度：O（N * log(N）)
//空间复杂度：N + log（N）--》O(N)
int main() {
	int arr[] = { 10,9,8,7,6,5,4,3,2 ,1 };
	int size = sizeof(arr) / sizeof(arr[0]);
	int* temp = (int*)malloc(sizeof(int) * size);
	if (!temp)
		return 0;
	MergeSort(arr, 0, size, temp);//[left,right)，下标，左闭右开
	SortPrint(arr, size);
	free(temp);
	temp = NULL;
	return 0;
}

#endif 